/*
 * @lc app=leetcode.cn id=494 lang=javascript
 *
 * [494] 目标和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {//背包问题
  let sum = nums.reduce((a, b) => a + b);
  if (sum < target || (sum - target) % 2 == 1) return 0;
  let diff = (sum - target) >> 1;
  //问题变为需要在全是正整数的数组nums中找到和为diff的总方法
  let dp = new Array(nums.length).fill(0);
  let count = 0;
  dp[0] = [0, nums[0]];
  if(nums[0]==diff)count++
  if(diff==0)count++
  for (let i = 1; i < nums.length; i++) {
    dp[i] = [];
    for (let item of dp[i - 1]) {
      if(item<=diff){
        dp[i].push(item)
      }
      if(item+nums[i]==diff)count++
      if(item+nums[i]<=diff){
        dp[i].push(item+nums[i])
      }
    }
  }
  return count;
};
// @lc code=end
findTargetSumWays([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],0)